package com.kenliang.algorithm.sort;

import java.util.Arrays;

/**
 * @author KenLiang
 * @description: 归并排序
 * todo 非递归模式
 * 时间复杂度O(N*logN) 空间复杂度O(N)
 * @date Created in 14:57 2021/1/2.
 */
public class MergeSort implements ISort {
    @Override
    public int[] sort(int[] in) {
        this.process(in, 0, in.length - 1);
        return in;
    }

    private void process(int[] in, int left, int right) {
        if (left == right) {
//            System.out.println(in[left]);
            return;
        }
        int mid = left + ((right - left ) >> 1);
        this.process(in, left, mid);
        this.process(in, mid+1, right);
        this.merge(in,left,mid,right);
    }

    //合并左右分支
    private void merge(int[] in,int left,int mid,int right) {
        int[] mergeArray = new int[right-left+1];

        int leftIndex = left;
        int mergeIndex = 0;
        int rightIndex = mid+1;
        while(leftIndex <= mid && rightIndex <= right){
            if (in[leftIndex] <= in[rightIndex]) {
                mergeArray[mergeIndex++] = in[leftIndex++];
            } else {
                mergeArray[mergeIndex++] = in[rightIndex++];
            }
        }

        if(leftIndex <= mid){
            for(int i = leftIndex;i<= mid;i++){
                mergeArray[mergeIndex++] = in[i];
            }
        }
        if(rightIndex <= right){
            for(int i = rightIndex;i<= right;i++){
                mergeArray[mergeIndex++] = in[i];
            }
        }
        for(int i=0;i<mergeArray.length;i++){
            in[left+i] = mergeArray[i];
        }
    }
}
